package listbyorder.access001_100.test44;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/5/31 19:43
 */
public class Solution2 {

    // 方法二： 暴力递归改动态规划
    public boolean isMatch(String s, String p) {
        if (p.equals("")) return s.equals("");
        int cs = s.length();
        int cp = p.length();
        boolean[][] dp = new boolean[cs + 1][cp + 1];
        for (int i = cs; i >= 0; i--) {
            for (int j = cp; j >= 0; j--) {
                if (i == cs) {
                    if (j < cp) {
                        dp[i][j] = p.charAt(j) == '*' && dp[i][j + 1];
                    } else {
                        dp[i][j] = true;
                    }
                } else if (j == cp) {
                    continue;
                } else if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?') {
                    dp[i][j] = dp[i + 1][j + 1];
                } else if (p.charAt(j) == '*') {
                    dp[i][j] = dp[i + 1][j] || dp[i + 1][j + 1] || dp[i][j + 1];
                }
            }
        }
        return dp[0][0];
    }

}
